package cn.cxq.learning.tree;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;

/**
 * 剑指offer
 * 从上往下打印二叉树
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：642511
 * 本题知识点： 队列 树
 *  算法知识视频讲解
 * 题目描述
 * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 * 示例1
 * 输入
 * 复制
 * {5,4,#,3,#,2,#,1}
 * 返回值
 * 复制
 * [5,4,3,2,1]
 */
public class FromUpToDownPrintBinaryTree {

    @Test
    public void testPrint(){
        TreeNode root = new TreeNode(8);

        TreeNode treeNode = root;

        treeNode.left = new TreeNode(4);
        treeNode.right = new TreeNode(12);
        treeNode.left.left = new TreeNode(2);
        treeNode.left.right = new TreeNode(6);
        treeNode.right.left = new TreeNode(10);
        treeNode.right.right = new TreeNode(14);
        treeNode.left.left.left = new TreeNode(1);
        treeNode.left.left.right = new TreeNode(3);
        treeNode.left.right.left = new TreeNode(5);
        treeNode.left.right.right = new TreeNode(7);
        treeNode.right.left.left = new TreeNode(9);
        treeNode.right.left.right = new TreeNode(11);
        treeNode.right.right.left = new TreeNode(13);
        treeNode.right.right.right = new TreeNode(15);

        ArrayList<Integer> print = PrintFromTopToBottom(root);
        System.out.println(print);
    }

    //思路：使用递归轻松解决
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        ArrayList<Integer> result = new ArrayList<>();

        if (root == null) return result;

        result.add(root.val);

        ArrayList<TreeNode> floorNode = new ArrayList<>();
        floorNode.add(root);

        PrintFromTopToBottom(result,floorNode);

        return result;
    }

    private void PrintFromTopToBottom(ArrayList<Integer> result, ArrayList<TreeNode> floorNode) {

        if (floorNode.isEmpty()) {
            return;
        }

        ArrayList<TreeNode> nextFloorNode = new ArrayList<>();
        for (TreeNode treeNode : floorNode) {
            if (treeNode == null) return;
            if (treeNode.left != null) {
                result.add(treeNode.left.val);
                nextFloorNode.add(treeNode.left);
            }
            if (treeNode.right!= null) {
                result.add(treeNode.right.val);
                nextFloorNode.add(treeNode.right);
            }
        }

        PrintFromTopToBottom(result,nextFloorNode);
    }
}



class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }
}